
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2304. -- [Apio2011]寻路 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2304: [Apio2011]寻路</h2><span class=green>Time Limit: </span>20 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>256 MB<br><span class=green>Submit: </span>159&nbsp;&nbsp;<span class=green>Solved: </span>56<br>[<a href='submitpage.php?id=2304'>Submit</a>][<a href='problemstatus.php?id=2304'>Status</a>][<a href='bbs.php?id=2304'>Discuss</a>]</center><h2>Description</h2><div class=content><p>TooDee是一块二维格子状的土地（就像著名的笛卡尔坐标系那样） ，在这里<br />
生活着很多可爱的Dee。Dee是像蜜蜂一样的小动物，它们只在二维活动，而且<br />
它们非常的文明开化。TooDee 的蜂窝和正常世界的蜂窝也是很不一样的，它们<br />
是矩形的且它们的边平行于TooDee的地理坐标系，就是说矩形的边或者是东西<br />
走向，或者是南北走向。 <br />
因为 Dees 是很高级的生物，它们有很多固定的飞行轨道，这些轨道由一些<br />
平行于坐标轴的线段组成，线段只会在经纬度都是整数的点相交。 Dee在TooDee<br />
飞行时必须遵守以下规则（请记住TooDee中所有点的经纬度都是整数）： <br />
1&nbsp; 如果当前在点(XS, YS)， 则下步只能飞到四个邻点&nbsp; (XS, YS &ndash; 1), (XS, YS + 1),&nbsp;&nbsp; <br />
(XS &ndash; 1, YS ), (XS + 1, YS )； <br />
2&nbsp; 不可以进入蜂巢； <br />
3&nbsp; 只能在蜂巢的角或者边上改变飞行方向； <br />
4&nbsp; 开始的时候可以向任何方向飞； <br />
今晚是公共财政大臣Deeficer的女儿的生日，她想尽早回家，请帮她找到最<br />
快的回家路径。假设她每秒可以飞行一个单位的距离。</p></div><h2>Input</h2><div class=content><p>每个测试点包含多组数据。 <br />
输入的第一行包含一个整数T，表示测试数据的组数。接下来依次描述这T<br />
组数据，相邻的两组之间使用一个空行分隔。测试数据不多于20组。 <br />
对于每组数据，第一行包含4个整数 xs, ys, xt, yt，表示Deeficer 的办公室和<br />
家的坐标分别为(xs, ys)和(xt, yt)。第二行包含一个整数n，表示蜂巢的个数。接下<br />
来的n行描述所有的蜂巢，其中第 i行包含 4 个整数xi1,&nbsp; yi1,&nbsp; xi2,&nbsp; yi2，表示第i个<br />
蜂巢两个对角的坐标分别为(xi1, yi1)和(xi2, yi2)。 <br />
任何两个蜂巢都不会相交，也不会接触（在角上也不会接触）。办公室和家<br />
处在不同的位置。每个蜂巢的面积为正。</p></div><h2>Output</h2><div class=content><p>对于每一组数据，输出一个整数，表示Deeficer 最快回家的时间（单位为秒），<br />
如果她无法按规则回家，则输出&ldquo;No Path&rdquo;。</p>
<p>对于100%的测试数据，1 &le; n &le; 1000，所有坐标都是不超过10^9<br />
的整数；</p></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>2 <br />
 <br />
1 7 7 8 <br />
2 <br />
2 5 3 8 <br />
4 10 6 7 <br />
 <br />
2 1 5 4 <br />
1 <br />
3 1 4 3 </span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>9 <br />
No Path <br />
 </span></div><h2>HINT</h2>
			<div class=content><p><p>数据为国际加国内综合版</p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=2304'>Submit</a>][<a href='problemstatus.php?id=2304'>Status</a>][<a href='bbs.php?id=2304'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
